package com.leetcode.No0023;

/**
 * 	public class ListNode {
 * 		int val;
 * 		ListNode next;
 * 		ListNode() {}
 * 		ListNode(int val) {
 * 			this.val = val;
 *      }
 * 		ListNode(int val, ListNode next) {
 * 			this.val = val;
 * 			this.next = next;
 *      }
 *  }
 *
 * @program: leetcode
 * @description: 合并K个升序链表
 * @author: wangzhihua
 * @date: 2021-07-24
 */
public class Solution01 {

	public ListNode mergeKLists(ListNode[] lists) {
		ListNode preNode = null; // previous Node
		ListNode ansNode = null; // answer Node
		while (whileCondition(lists)) {
			int nextNodeIndex = 0;
			int nextNodeValue = Integer.MAX_VALUE;
			for (int i = 0; i < lists.length; ++i) {
				if (lists[i] == null) {
					continue;
				}
				if (nextNodeValue > lists[i].val) {
					nextNodeValue = lists[i].val;
					nextNodeIndex = i;
				}
			}
			if (preNode == null) {
				preNode = new ListNode(nextNodeValue);
				ansNode = preNode;
			} else {
				preNode.next = new ListNode(nextNodeValue);
				preNode = preNode.next;
			}
			lists[nextNodeIndex] = lists[nextNodeIndex].next;
		}
		return ansNode;
	}

	public boolean whileCondition(ListNode[] lists) {
		for (ListNode node : lists) {
			if (node != null) {
				return true;
			}
		}
		return false;
	}

	public class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) {
			this.val = val;
		}
		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

}
